МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національній університет "Львівська політехніка" / Алгоритми побудови дерев Звіт до лабораторної роботи №1 з курсу "Дискретні моделі в САПР"  1.Мета роботи: вивчення алгоритмів рішення задач побудови остових дерев. 2.Короткі теоретичні відомості. Для того, щоб розглянути алгоритми побудови дерев нагадаємо деякі основні положення теорії графів. Графом G називають скінчену множину V з нерефлексивним симетричним відношенням R на V. Визначим E як множину симетричних пар в R. Кожний елемент V називають вершиною. Кожний елемент Е називають ребром, а E множиною ребер G. Граф називається зв’язним, якщо в ньому для будь-якої пари вершин знайдеться ланцюг, який їх з’єднує, тобто, якщо по ребрах (дугах) можна попасти з будь-якої вершини в іншу. Цикл - це ланцюг, в якого початкова і кінцева точки співпадають. Дерево - це зв’язний граф без циклів.Лісом називається будь-яка сукупність дуг (ребер) інцидентних до вершин, які не містять циклів. Таким чином, ліс складається з одного або більше дерев. Остовним деревом графа називається будь-яке дерево, яке утворене сукупністю дуг, які включають всі вершини графа. В графі, який показано на рис.1, сукупність дуг утворює остовне дерево, так як вона включає всі вершини даного графа а,b,c,d. Будь-який зв’язний граф має остовне дерево. Коренем орієнтованого дерева (прадерева) називається його вершина, в яку не входить жодна з дуг. Орієнтований ліс визначається як звичайний, тільки складається не з простих дерев, а орієнтованих. Остовним орієнтованим деревом називається орієнтоване дерево, яке одночасно є і остовим деревом. Остовним орієнтованим лісом називається орієнтований ліс, який включає всі вершини відповідного графа. Вага дерева - це сума ваг його ребер. Поставимо у відповідність кожній дузі (х,у) графа G вагу а(х,у). Вага орієнтованого лісу (або орієнтованого дерева) визначається як сума ваг дуг, що входять в даний ліс (дерево). Максимальним орієнтованим лісом графа G називається орієнтований ліс графа G з максимально можливою вагою. Максимальним орієнтованим деревом графа G називається орієнтоване дерево графа G з максимально можливою вагою. Мінімальні орієнтовані ліс і дерево визначаються аналогічним чином. Алгоритм Борувки. Це алгоритм знаходження мінімального остового дерева в графі. Вперше був опублікований в 1926 році Отакаром Борувкой, як метод знаходження оптимальної електричної мережі в Моравії. Робота алгоритму складається з декількох ітерацій, кожна з яких полягає в послідовному додаванні ребер до остового лісу графа, до тих пір, поки ліс не перетвориться на дерево, тобто, ліс, що складається з однієї компоненти зв'язності. У псевдокоді, алгоритм можна описати так: Спочатку, нехай T - порожня множина ребер (представляє собою остовий ліс, до якого кожна вершина входить в якості окремого дерева). Поки T не є деревом (поки число ребер у T менше, ніж V-1, де V -кількість вершин у графі): Для кожної компоненти зв'язності (тобто, дерева в остовому лісі) в підпункті з ребрами T, знайдемо ребро найменшої ваги, що зв'язує цю компоненту з деякої іншої компонентою зв'язності. (Передбачається, що ваги ребер різні, або як-то додатково впорядковані так, щоб завжди можна було знайти єдине ребро з мінімальною вагою). Додамо всі знайдені ребра в множину T.Отримана множина ребер T є мінімальним остовим деревом вхідногографа. 3.Результати виконання. Варіант 9. Алгоритм Борувки. Рис.1. Початковий граф. Рис.2. Знаходження безпечних ребер для кожної вершини. Рис.3. Додавання безпечних ребер до МОЛ. Рис.4. знаходження безпечних ребер для вершин. / Рис.5. МОД = 71. Текст програми на мові Java:public class BoruvkaAlg { static int verA, verB, edgeWeight; //Вершина 1,2 і вага ребра між ними static int weightArray[][] ; //Масив для збереження ваг між  static int passedVertices[]; //Пройдені вершини static int currentVertices[]; ...